#pragma once
#include <cstdlib>
#include <iostream>

using namespace std;

class Node
{
public:
	Node(int v)
	{
		val = v;
		left = right = nullptr;
	}

public:
	int val;
	Node* left;
	Node* right;
};

class BST
{
public:
	BST() : root(nullptr){}
	void ShowTree();

	void Add(int v);
	bool Del(int v);
	int GetMax();
	int GetMin();

	void PreTraverseR()
	{
		cout << "pre traverse R:";
		_PreTraverseR(root);
		cout << endl;
	}
	void MidTraverseR()
	{
		cout << "mid traverse R:";
		_MidTraverseR(root);
		cout << endl;
	}
	void PostTraverseR()
	{
		cout << "post traverse R:";
		_PostTraverseR(root);
		cout << endl;
	}

	void PreTraverse()
	{
		cout << "pre traverse N:";
		_PreTraverse(root);
		cout << endl;
	}

	void MidTraverse()
	{
		cout << "mid traverse N:";
		_MidTraverse(root);
		cout << endl;
	}

	void PostTraverse()
	{
		cout << "post traverse N:";
		_PostTraverse(root);
		cout << endl;
	}

	void LevelTraverse()
	{
		cout << "Level traverse N:";
		_LevelTraverse(root);
		cout << endl;
	}
	
	
private:
	int _GetDepth(Node* node);
	void _MidAccessPrintNode(int depth, Node* node);

	// Traverse
	void _PreTraverseR(Node* node);
	void _MidTraverseR(Node* node);
	void _PostTraverseR(Node* node);

	void _PreTraverse(Node* node);
	void _MidTraverse(Node* node);
	void _PostTraverse(Node* node);

	void _LevelTraverse(Node* node);

	//delete
	Node* _DelNode(Node* n);

private:
	Node* root;
};
